package com.wss.lsl.test.driven.arithmetic;

/**
 * 计算逆序对的数量
 * 
 * @author weiss
 *
 */
public class ReverseTuple {

	public static int count(int[] data, int begin, int end) {
		int count = 0;
		if (begin < end) {
			int middle = (begin + end) / 2;
			count += count(data, begin, middle);
			count += count(data, middle + 1, end);
			count += merge(data, begin, middle, end);
		}

		return count;
	}

	public static int merge(int[] data, int begin, int middle, int end) {

		int count = 0;
		for (int i = begin; i <= middle; i++) {
			for (int j = middle + 1; j <= end; j++) {
				if (data[i] > data[j]) {
					count++;
				}
			}
		}

		return count;
	}
}
